package array

// 题目1
// 找出数组中重复的数字
// 在一个长度为n的数组中所有的数字都在0~n-1的范围内，数组中某些数字是重复的
// 但不知道哪些重复，也不知道几次，请找出数组中任意一个重复的数字
// [2,3,1,0,2,5,3] 应该输出 2 或 3

// 解法一: 先排序 然后从0遍历很容易找到重复元素

// 解法三：使用map存储index，value 很容易找到重复元素
func Duplicate13(a []int) int {
	if len(a) <= 1 {
		return -1
	}
	var dict = map[int]bool{}
	for i := 0; i < len(a); i++ {
		_, ok := dict[a[i]]
		if ok {
			return a[i]
		} else {
			dict[a[i]] = true
		}
	}
	return -1
}

// 解法二
// 从头到尾扫描数组中的每个数字，当扫描到下标为i的数字时，比较这个数字m是不是等于i
// 如果是，继续扫描，否则再拿它和第m位置数字进行比较，如果相等就找到了第一个重复的数字
// 否则交互当前位置数字和第m位置的数字
// 只有当i位置数字等于i的时候i++

func Duplicate12(a []int) int {
	if len(a) <= 1 {
		return -1
	}
	for i := 0; i < len(a); {
		if a[i] != i {
			if a[i] == a[a[i]] {
				return a[i]
			}
			a[a[i]], a[i] = a[i], a[a[i]]
		} else {
			i++
		}
	}
	return -1
}

// 题目二 ：在题目一基础上 要求不修改原数组求出任意一个重复数

// 解法一：构造一个辅助数组然后使用题目一的解法二，缺点是

func Duplicate20(a []int) int {
	tmp := make([]int, len(a))
	copy(tmp, a)
	return Duplicate12(tmp)
}

// 解法二：二分查找
// 时间复杂度为 nlogn 空间复杂度为 o1

func Duplicate21(a []int) int {
	if len(a) == 0 {
		return -1
	}
	var start = 1
	var end = len(a) - 1
	for end >= start {
		var middle = ((end - start) >> 1) + start
		var count = countRange(a, start, middle)
		if end == start {
			if count > 1 {
				return start
			} else {
				break
			}
		}
		if count > (middle - start + 1) { // count 超过左区间长度
			end = middle
		} else { // count 超过右区间长度
			start = middle + 1
		}
	}
	return -1
}

// 对数组a在start和end之间进行统
func countRange(a []int, start, end int) int {
	if len(a) == 0 {
		return 0
	}
	var count = 0
	for i := 0; i < len(a); i++ {
		if a[i] >= start && a[i] <= end {
			count++
		}
	}
	return count
}
